package com.zhn;

/**
 * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 2
 * 输出：[0,1,1]
 * 解释：
 * 0 --> 0
 * 1 --> 1
 * 2 --> 10
 */
//        1: 0001     3:  0011      0: 0000
//        2: 0010     6:  0110      1: 0001
//        4: 0100     12: 1100      2: 0010
//        8: 1000     24: 11000     3: 0011
//        16:10000    48: 110000    4: 0100
//        32:100000   96: 1100000   5: 0101
// 由上可见：
//        1、如果 i 为偶数，那么f(i) = f(i/2) ,因为 i/2 本质上是i的二进制左移一位，低位补零，所以1的数量不变。
//        偶数 +1 后最低位变为1且不会进位，所以奇数比它上一个偶数bit上多一个1，即 f(i) = f(i/2) + 1。

public class CountBits {
    public int[] countBits(int n) {
        int[] dp = new int[n+1];
        dp[0] = 0;
        for(int i = 1;i <= n;++i){
            if(i%2 == 0){
                dp[i] = dp[i/2];
            }else {
                dp[i] = dp[i / 2] + 1;
            }
        }
        return dp;
    }
}
